/**
 * @param {number[]} nums
 * @return {number}
 */
 var maxCoins = function(nums) {
    const n = nums.length;
    const rec = [...Array(n + 2)].map(x => Array(n + 2).fill(0));
    const val = [1,...nums,1];
    for(let i = n - 1; i >= 0; i--){
        for(let j = i + 2; j <= n + 1; j++){
            for(let k = i + 1; k < j; k++){
                let sum = val[i] * val[k] * val[j];
                sum += rec[i][k] + rec[k][j];
                rec[i][j] = Math.max(rec[i][j],sum);
            }
        }
    }
    return rec[0][n + 1];
};
let nums = [3,1,5,8];
// nums = [1,5];
console.log(maxCoins(nums));